ATC B - Union Find
https://atcoder.jp/contests/atc001/tasks/unionfind_a
提出
code: python
n, q = map(int, input().split())
pab = list(map(int, input().split())) for _ in range(q)
class UnionFind:
def __init__(self, n):
# 親要素のノード番号を格納。parentx == xの時そのノードは根(最初は全て根)
self.parent = i for i in range(n)
# 木の高さを格納する（初期状態では0）
self.rank = 0 * n
# 人間の数
self.size = 1 * n
# 検索
def find(self, x):
# 根ならその番号を返す
if self.parentx == x:
return x
# 根でないなら、親の要素で再検索
else:
# 走査していく過程で親を書き換える(return x が代入される)
self.parentx = self.find(self.parentx)
return self.parentx
# 併合
def union(self, x, y):
# 根を探す
x = self.find(x)
y = self.find(y)
if x == y:
return
# 木の高さを比較し、低いほうから高いほうに辺を張る
if self.rankx < self.ranky:
self.parentx = y
self.sizey += self.sizex
else:
self.parenty = x
self.sizex += self.sizey
# 木の高さが同じなら片方を1増やす
if self.rankx == self.ranky:
self.rankx += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
UF = UnionFind(n)
for p, a, b in pab:
if p == 0:
UF.union(a, b)
else:
print("Yes") if UF.same(a, b) else print("No")
テーマ
#UnionFind
蟻本 2-4 食物連鎖